/*
	动态规划
	求两个序列的最长的公共序列
	如 X=(a,b,c,b,d,a,b)
	   Y=(b,d,c,a,b,a)
	   最长公共序列为
	   Z=(b,c,b,a)

	   递归思想
	   c[i][j] = 0                          i = 0或j = 0
	           = c[i-1][j-1] + 1            i,j > 0 且 Xi = Yi
	           = max{c[i][j-1], c[i-1][j]}  i,j > 0 且 Xi != Yi
*/
//自下而上构造备忘录矩阵
void LCSLength(int m, int n, char *x, char *y, int **c, int **b)
{//m,n分别为X,Y的长度，c矩阵记录子问题的长度，b矩阵记录子问题的类型
	int i,j;
	for (i = 0; i<=m; i++)
	{
		c[i][0] = 0;
	}

	for (i = 1; i<=n; i++)
	{
		c[0][j] = 0;
	}

	for (i = 1; i<=m; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if (x[i] == y[j])
			{
				c[i][j] = c[i-1][j-1]+1;
				b[i][j] = 1;
			}
			else if (c[i-1][j] >= c[j][j])
			{
				c[i][j] = c[i-1][j];
				b[i][j] = 2;
			}
			else
			{
				c[i][j] = c[i][j-1];
				b[i][j] = 3;
			}
		}
	}

}//时间性能O(mn),空间性能O(1)

//构造最小序列,按照类型递归表达即可
void LCS(int i, int j, char *x, int **b)
{
	if (i = 0 || j = 0)
		return;

	if (b[i][j] = 1)
	{
		LCS(i-1, j, x, b);
		printf("%s",b[i][j]);
	}
	else if (b[i][j] = 2)
		LCS(i-1, j, x ,b);
	else
		LCS(i, j-1, x ,b);
	
}